
/*
 * perceptron.c
 *
 * This file implements the simulated perceptron branch predictor from:
 *
 * Jimenez, D. A. & Lin, C., Dynamic branch prediction with perceptrons,
 * Proceedings of the Seventh International Symposium on High Performance
 * Computer Architecture (HPCA), Monterrey, NL, Mexico 2001
 *
 * The #define's here specify a perceptron predictor with a history
 * length of 24, 163 perceptrons, and  8-bit weights.  This represents
 * a hardware budget of (24+1)*8*163 = 32600 bits, or about 4K bytes,
 * which is comparable to the hardware budget of the Alpha 21264 hybrid
 * branch predictor.
 *
 * There are three important functions defined in this file:
 * 
 * 1. void initialize_perceptron_predictor (void);
 * Initialize the perceptron predictor
 *
 * 2. perceptron_state *perceptron_dir_lookup (unsigned int);
 * Get a branch prediction, given a branch address.  This function returns a
 * pointer to a 'perceptron_state' struct, which contains the prediction, the
 * perceptron output, and other information necessary for using and updating
 * the predictor.  The first member of a 'perceptron_state' struct is a char
 * that is asunsigned 3 if the branch is predicted taken, 0 otherwise; this way,
 * a pointer to 'perceptron_state' can be cast to (char *) and passed around
 * SimpleScalar as though it were a pointer to a pattern history table entry.
 *
 * 3. void perceptron_update (perceptron_state *, int);
 * Update the branch predictor using the 'perceptron_state' pointer 
 * returned by perceptron_dir_lookup() and an int that is 1 if the branch
 * was taken, 0 otherwise.
 */

#include <stdio.h>
#include <cassert>
#include <string.h>
#include <inttypes.h>

using namespace std;
#include "cbp3_def.h"
#include "cbp3_framework.h"

/* history length for the global history shift register */

#define PERCEPTRON_HISTORY	59
// old value was 24.

/* number of perceptrons */

#define NUM_PERCEPTRONS		1100
// old value was 163

/* number of bits per weight */

#define PERCEPTRON_BITS		8

/* maximum and minimum weight values */

#define MAX_WEIGHT		((1<<(PERCEPTRON_BITS-1))-1)
#define MIN_WEIGHT		(-(MAX_WEIGHT+1))

/* threshold for training */

#define THETA			((int) (1.93 * PERCEPTRON_HISTORY + 14))

/* size of buffer for keeping 'perceptron_state' for update */

#define NUM_UPDATE_ENTRIES	100

/* perceptron data structure */

typedef struct {
	int	
		/* just a vector of integers */

		weights[PERCEPTRON_HISTORY+1];
} perceptron;

/* 'perceptron_state' - stores the branch prediction and keeps information
 * such as output and history needed for updating the perceptron predictor
 */
typedef struct {

	int
		/* prediction: 1 for taken, 0 for not taken */

		prediction,

		/* perceptron output */

		output;

                 uint32_t
		/* value of the history register yielding this prediction */

		history;	       	

		/* pointer to the perceptron yielding this prediction */

		perceptron *perc;
} perceptron_state;


	/* table of perceptrons */

perceptron perceptrons[NUM_PERCEPTRONS];

perceptron_state 
	/* state for updating perceptron predictor */

	perceptron_state_buf[NUM_UPDATE_ENTRIES];

int 
	/* index of the next "free" perceptron_state */

	perceptron_state_buf_ctr;

/* value of the history register at fetch and retire respectively */

       uint32_t brhistory_fetch;
       uint32_t brhistory_retire;

/* initialize a single perceptron */

void initialize_perceptron (perceptron *p) {
	int	i;

	for (i=0; i<=PERCEPTRON_HISTORY; i++) p->weights[i] = 0;
}

/* update the perceptron predictor */

void perceptron_update (perceptron_state *u, int taken) {
	int	
		i,
		y, 
		*w;

	uint32_t
		mask, 
		history;

	/* update the real global history shift register */


	/* if the output of the perceptron predictor is outside of
	 * the range [-THETA,THETA] *and* the prediction was correct,
	 * then we don't need to adjust the weights
	 */

	if (u->output > THETA)
		y = 1;
	else if (u->output < -THETA)
		y = 0;
	else
		y = 2;
	if (y == 1 && taken) return;
	if (y == 0 && !taken) return;

	/* w is a pointer to the first weight (the bias weight) */

	w = &u->perc->weights[0];

	/* if the branch was taken, increment the bias weight w_0,
	 * else decrement it, with saturating arithmetic
	 */

	if (taken)
		(*w)++;
	else
		(*w)--;
	if (*w > MAX_WEIGHT) *w = MAX_WEIGHT;
	if (*w < MIN_WEIGHT) *w = MIN_WEIGHT;

	/* now w points to the next weight w_1*/

	w++;

	/* get the history that led to this prediction */

	history = u->history;

	/* for each weight and corresponding bit in the history register... */

	for (mask=1,i=0; i<PERCEPTRON_HISTORY; i++,mask<<=1,w++) {

		/* if the i'th bit in the history positively correlates
		 * with this branch outcome, increment the corresponding 
		 * weight, else decrement it, with saturating arithmetic
		 */

		if (!!(history & mask) == taken) {
			(*w)++;
			if (*w > MAX_WEIGHT) *w = MAX_WEIGHT;
		} else {
			(*w)--;
			if (*w < MIN_WEIGHT) *w = MIN_WEIGHT;
		}
	}
}


/* get a prediction in fetch stage*/

perceptron_state *perceptron_dir_lookup_fetch (unsigned int address) {
	int	
		index,
		i,
		output,
		*w;
	uint32_t
		mask;
	perceptron 
		*p;
	perceptron_state
		*u;
          /* get a pointer to the next "free" perceptron_state,
	 * bumping up the pointer (and possibly letting it wrap around) 
	 */


       u = &perceptron_state_buf[perceptron_state_buf_ctr++];
	if (perceptron_state_buf_ctr >= NUM_UPDATE_ENTRIES)
		perceptron_state_buf_ctr = 0;

	/* hash the address to get an index into the table of perceptrons */

	index = address % NUM_PERCEPTRONS;

	/* get pointers to that perceptron and its weights */

	p = &perceptrons[index];
	w = &p->weights[0];

	/* initialize the output to the bias weight, and bump the pointer
	 * to the weights
	 */

	output = *w++;

	/* find the (rest of the) dot product of the history register
	 * and the perceptron weights.  note that, instead of actually
	 * doing the expensive multiplies, we simply add a weight when the
	 * corresponding branch in the history register is taken, or
	 * subtract a weight when the branch is not taken.  this also lets
	 * us use binary instead of bipolar logic to represent the history
	 * register
	 */
	for (mask=1,i=0; i<PERCEPTRON_HISTORY; i++,mask<<=1,w++) {
		if (brhistory_fetch & mask)
			output += *w;
		else
			output += -*w;
	}
        u->output = output;
	u->perc = p;
        u->history = brhistory_fetch;
	u->prediction = output >= 0;

	return u;
}

/* get a prediction in retire stage */

perceptron_state *perceptron_dir_lookup_retire (unsigned int address) {
	int	
		index,
		i,
		output,
		*w;
	uint32_t
		mask;
	perceptron 
		*p;
	perceptron_state
		*u;

        /* get a pointer to the next "free" perceptron_state,
	 * bumping up the pointer (and possibly letting it wrap around) 
	 */


        u = &perceptron_state_buf[perceptron_state_buf_ctr++];
	if (perceptron_state_buf_ctr >= NUM_UPDATE_ENTRIES)
		perceptron_state_buf_ctr = 0;

	/* hash the address to get an index into the table of perceptrons */

	index = address % NUM_PERCEPTRONS;

	/* get pointers to that perceptron and its weights */

	p = &perceptrons[index];
	w = &p->weights[0];

	/* initialize the output to the bias weight, and bump the pointer
	 * to the weights
	 */

	output = *w++;

	/* find the (rest of the) dot product of the history register
	 * and the perceptron weights.  note that, instead of actually
	 * doing the expensive multiplies, we simply add a weight when the
	 * corresponding branch in the history register is taken, or
	 * subtract a weight when the branch is not taken.  this also lets
	 * us use binary instead of bipolar logic to represent the history
	 * register
	 */
	for (mask=1,i=0; i<PERCEPTRON_HISTORY; i++,mask<<=1,w++) {
		if (brhistory_retire & mask)
			output += *w;
		else
			output += -*w;
	}
        u->output = output;
	u->perc = p;
	u->prediction = output >= 0;

	return u;
}



/* initialize the perceptron predictor */

void PredictorInit() {
	int	i;
	brhistory_fetch = 0;
	brhistory_retire = 0;
        perceptron_state_buf_ctr = 0;
	for (i=0; i<NUM_PERCEPTRONS; i++)
		initialize_perceptron (&perceptrons[i]);
}

void PredictorReset() {
    printf("Predictor: perceptron\n"
		   "config: history=%d; bits_per_perceptron=%d; num_perceptrons=%d,"
		   "cost: %d KB\n", 
		   PERCEPTRON_HISTORY,PERCEPTRON_BITS,NUM_PERCEPTRONS,
		   ((PERCEPTRON_HISTORY+1)*PERCEPTRON_BITS*NUM_PERCEPTRONS/(8*1024)) );

	PredictorInit();
}

void PredictorRunACycle() {
	// note only predicts conditional branches

   // get info about what uops are processed at each pipeline stage
    const cbp3_cycle_activity_t *cycle_info = get_cycle_info();

    // make prediction at fetch stage
    for (int i = 0; i < cycle_info->num_fetch; i++) {
        uint32_t fe_ptr = cycle_info->fetch_q[i];
        const cbp3_uop_dynamic_t *uop = &fetch_entry(fe_ptr)->uop;

        if ( uop->type & IS_BR_CONDITIONAL) {
        	perceptron_state *st = perceptron_dir_lookup_fetch( uop->pc ); // TODO: unsafe conversion?
              // report prediction:
            // you need to provide direction predictions for conditional branches,
            // targets of conditional branches are available at fetch stage.
            // for indirect branches, you need to provide target predictions.
            // you can report multiple predictions for the same branch
            // the framework will use the last reported prediction to calculate 
            // misprediction penalty
           assert(report_pred(fe_ptr, false, st->prediction));
        }
  // update fetch branch history
        if (uop->type & IS_BR_CONDITIONAL)
            brhistory_fetch = (brhistory_fetch << 1) | (uop->br_taken ? 1 : 0);
        else if (uop_is_branch(uop->type))
            brhistory_fetch = (brhistory_fetch << 1) | 1;
           }

    for (int i = 0; i < cycle_info->num_retire; i++) {
        uint32_t rob_ptr = cycle_info->retire_q[i];
        const cbp3_uop_dynamic_t *uop = &rob_entry(rob_ptr)->uop;

        if ( uop->type & IS_BR_CONDITIONAL ) {

	        perceptron_state *st = perceptron_dir_lookup_retire( uop->pc );
        	perceptron_update( st, uop->br_taken );
        }

     if (uop->type & IS_BR_CONDITIONAL)
            brhistory_retire = (brhistory_retire << 1) | (uop->br_taken ? 1 : 0);
        else if (uop_is_branch(uop->type))
            brhistory_retire = (brhistory_retire << 1) | 1;

    }
}

void PredictorRunEnd() {
	// empty on purpose
}

void PredictorExit() {
	// empty on purpose
}


///

